/**
 * @file 0-1 背包问题
 * @description 给你⼀个可装载重量为 W 的背包和 N 个物品，每个物品有重量和价值两个属性。其中第 i 个物品的重量为 wt[i] ，
 * 价值为 val[i] ，现在让你⽤这个背包装物品，最多能装的价值是多少？
 */
N = 3
W = 4
wt = [2, 1, 3]
val = [4, 2, 3]

/**
 * 求最大背包价值
 * @param W 背包重量
 * @param N N个物品
 * @param wt 物品重量数组
 * @param val 物品价值数组
 */
function knapsack(W, N, wt, val) {
    const dp = Array(N + 1).fill(Array(W + 1).fill(0));
    for (let i = 1; i <= N; i++) {
        for (let w = 1; w <= W; w++) {
            if (w - wt[i - 1] < 0) {
                // 超重的情况下不能装入背包
                dp[i][w] = dp[i - 1][w]
            } else {
                // 择优选择装入背包
                dp[i][w] = Math.max(
                    dp[i - 1][w - wt[i - 1]] + val[i - 1],
                    dp[i - 1][w],
                );
            }
        }
        console.log(dp);
    }
    return dp[N][W];
}

console.log(knapsack(W, N, wt, val));

